//
// Description: 552. 学生出勤记录 II
// Created by Loading on 2021/8/18.
//

#include <bits/stdc++.h>

using namespace std;

int checkRecord(int n) {
    if (n == 1) {
        return 3;
    }
    constexpr int MOD = 1e9 + 7;
    // dp[i][j][k] 表示 第 i 天，出现 j 个 'A'，且连续出现 k 个 'L' 的情况总数
    /* 可以优化为二维 dp，因为 i 只与 i - 1 有关，但是要使用数组，因为 vector 拷贝超时 */
    int dp[2][3];
    memset(dp, 0, sizeof dp);
    // 第一天，初始化
    dp[0][0] = dp[1][0] = dp[0][1] = 1;

    for (int i = 2; i <= n; ++i) {
        // 临时 dp 数组，缓存最新计算结果
        int dpTemp[2][3];
        memset(dpTemp, 0, sizeof dpTemp);
        // 第 i 天为 'A'，连续 'L' 数清零，前边不能出现 'A'，且连续不能超过 2 个 'L'
        for (int k = 0; k <= 2; ++k) {
            dpTemp[1][0] = (dpTemp[1][0] + dp[0][k]) % MOD;
        }
        // 第 i 天为 'L'，连续 'L' 从 1 开始，前边可以出现 0~1 个 'A'，且连续不能超过 1 个 'L'
        for (int j = 0; j <= 1; ++j) {
            for (int k = 1; k <= 2; ++k) {
                dpTemp[j][k] = (dpTemp[j][k] + dp[j][k - 1]) % MOD;
            }
        }
        // 第 i 天为 'P'，连续 'L' 清零，前边可以出现 0~1 个 'A'，且连续不能超过 2 个 'L'
        for (int j = 0; j <= 1; ++j) {
            for (int k = 0; k <= 2; ++k) {
                dpTemp[j][0] = (dpTemp[j][0] + dp[j][k]) % MOD;
            }
        }
        /* 使用 vector 会超时 */
        memcpy(dp, dpTemp, sizeof dp);
    }

    int res = 0;
    for (int j = 0; j <= 1; ++j) {
        for (int k = 0; k <= 2; ++k) {
            res = (int) ((res + dp[j][k]) % MOD);
        }
    }
    return res;
}

int main() {
    int n = 10;
    int res = checkRecord(n);
    cout << res << endl;
}